ix, 471 pages : 24 cm

"This volume contains the proceedings of the Ninth Conference on Fundamentalsof Computation Theory (FCT 93) held in Szeged, Hungary, in August 1993. The conference was devoted to a broad range of topics including: - Semanticsand logical concepts in the theory of computing and formal specification - Automata and formal languages - Computational geometry, algorithmic aspects of algebra and algebraic geometry, cryptography - Complexity (sequential, parallel, distributed computing, structure, lower bounds, complexity of analytical problems, general concepts) - Algorithms (efficient, probabilistic, parallel, sequential, distributed) - Counting and combinatorics in connection with mathematical computer science The volume contains the texts of 8 invitedlectures and 32 short communications selected by the international program committee from a large number of submitted papers."--PUBLISHER'S WEBSITE

Includes bibliographical references

Rewriting, Mobius Functions and Semi-Commutations / V. Diekert -- Simulations between Different Models of Parallel Computers / M. Dietzfelbinger -- Dense and Disjunctive Properties of Languages / M. Ito -- The Hierarchy of Codes / H. Jurgensen and S. Konstantinidis -- Five Facets of Hyperedge Replacement Beyond Context-Freeness / H.-J. Kreowski -- An Action Structure for Synchronous [pi]-Calculus / R. Milner -- AC[superscript 0] Circuit Complexity. A Survey of Lower Bounds / R. Pudlak -- Pattern Languages: Problems of Decidability and Generation / A. Salomaa -- General Solution of Mirror Equation / H. Abdulrab and M. Maksimenko -- Decidability of Equivalence for Linear Letter to Letter Top-Down Tree Transducers / Y. Andre and F. Bossut -- Translations Between Flowchart Schemes and Process Graphs / J.A. Bergstra and Gh. Stefinescu -- Local Equational Logic / V.E. Cazanescu -- Liveness of Weighted Circuits and the Diophantine Problem of Frobenius / P. Chrzastowski-Wachtel and M. Raczunas -- Context-Free Graph Grammars: Separating Vertex Replacement from Hyperedge Replacement / B. Courcelle -- Formal Languages Consisting of Primitive Words / P. Domosi, S. Horvath, M. Ito, L. Kaszonyi and M. Katsura -- Undecidability of the Surjectivity Problem for 2D Cellular Automata: A Simplified Proof / B. Durand -- Efficient Interpretation of State Charts / J. Ebert -- Implementation of a Universal Unification Algorithm for Macro Tree Transducers / H. Fassbender -- Finding Maximum Convex Polygons / P. Fischer -- Approximations with Axis-Aligned Rectangles / P. Fischer, K.-U. Hoffgen, H. Lefmann and T. Luczak -- Vector Sequence Analysis and Full Weak Safety for Concurrent Systems / M. Girkar and R. Moll -- Does Transitivity Help? On the Complexity of Poset Properties / H.D. Groger -- Generalized Topological Sorting in Linear Time / T. Hagerup and M. Maas -- Easily Checked Self-Reducibility / L.A. Hemachandra and R. Silvestri -- On the Complexities of Linear LL(1) and LR(1) Grammars / M. Holzer and K.-J. Lange -- On the Relation Between Firing Sequences and Processes of Petri Nets / D.V. Hung and T.V. Dung -- Maximum Covering with D Cliques / K. Jansen, P. Scheffler and G. Woeginger -- Monotonically Labelled Ordered Trees and Multidimensional Binary Trees / R. Kemp -- Maximum Path Length Pumping Lemma for Edge-Replacement Languages / S. Kuske -- Regular Approximations to Shuffle Products of Context-Free Languages, and Convergence of their Generating Functions / R.S. Maier and R. Schott -- The Equational Theory of a Boolean Monad / E.G. Manes -- Non Erasing Turing Machines: A Frontier Between a Decidable Halting Problem and Universality / M. Margenstern -- On Scattered Syntactic Monoids / A. Mateescu -- Regular Tree Languages without Unary Symbols are Star-Free / A. Potthoff and W. Thomas -- One-Way Cellular Automata on Cayley Graphs / Z. Roka -- On Tree Pattern Unification Problems / P. Ruzicka and I. Privara -- Structural Equivalence and ETOL Grammars / K. Salomaa, D. Wood and S. Yu -- A Hierarchy of Deterministic Top-Down Tree Transformations / G. Slutzki and S. Vagvolgyi -- Synthesis of O(lg n) Testable Trees / H. Wu -- On the Learnability of a Restricted Predicate Formulae / J. Yin and Z. Hong

plus-circle Add Review

comment

Reviews